package tree

import "math"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/*
时间复杂度:O(N) 每个节点访问一次
空间复杂度:O(N) 递归调用层等于二叉树高度，最坏情况下树呈链状
*/

func maxPathSum(root *TreeNode) int {
	// 无论最大路径是那条，一定都是可以看作经过某一棵子树根节点的路径
	// 也就是说，可以设置一个函数maxGain(node), 计算以node为根节点的子树中经过该根节点的路径的最大值
	// 则在递归过程中会求出所有子树的maxGain(node),求其中的最大值即可
	maxSum := math.MinInt32
	var maxGain func(node *TreeNode) int
	maxGain = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		// 求出左右子树的maxGain，然后加上node.Val求出node对应的maxGain
		// 这里需要注意，如果左右子树的maxGain为负数，则不需要累加到最终node的maxGain中
		leftGain := max(maxGain(node.Left), 0)
		rightGain := max(maxGain(node.Right), 0)

		// 递归过程会求出所有节点的maxGain,取最大的一个即可
		maxSum = max(maxSum, node.Val+leftGain+rightGain)

		// 返回node的maxGain
		return node.Val + max(leftGain, rightGain)
	}
	maxGain(root)
	return maxSum
}
